package com.cjm.algorithm.queue;

import java.util.*;

public class MaxSlidingWindow239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        int n = nums.length, m = n - k + 1, idx = 0;
        int[] ans = new int[m];
        for (int i = 0; i < n; i++) {
            q.add(new int[]{i, nums[i]});
            if (i >= k - 1) {
                while (q.peek()[0] <= i - k) q.poll();
                ans[idx++] = q.peek()[1];
            }
        }
        return ans;
    }
    /**
     * 遍历数组， 将数存入在双向队列中， 并用L，R来标记窗口的左边界和右边界。队列中保存的并不是真的数，而是该
     * 数值对应的数组下标位置， 并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大， 则需要弹出队尾值，
     * 直到队列重新满足从大到小的要求。刚开始遍历时， L，R都为0， 有一个形成窗口的过程， 此过程没有最大值， L
     * 不动， R向右移。当窗口大小形成时， L和R一起向右移， 每次移动时， 判断队首的值的数组下标是否在[L,R]中，
     * 如果不在则需要弹出队首的值， 当前窗口的最大值即为队首的数。
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums == null || nums.length < 2) return nums;

        LinkedList<Integer> queue = new LinkedList<>();

        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            queue.addLast(i);
            if (queue.peek() <= i - k) {
                queue.poll();
            }
            if (i + 1 >= k) {
                result[i + 1 - k] = nums[queue.peek()];
            }
        }
        return result;
    }
}
